package problem.year2021.january;

import java.util.*;

/**
 * 给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
 * <p>
 * 现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
 * <p>
 * 合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。账户本身可以以任意顺序返回。
 * 示例 1：
 * <p>
 * 输入：
 * accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
 * 输出：
 * [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],
 * ["John", "johnnybravo@mail.com"],
 * ["Mary", "mary@mail.com"]]
 * 解释：
 * 第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "johnsmith@mail.com"。
 * 第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
 * 可以以任何顺序返回这些列表，例如答案 [['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
 * ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正确的。
 * 提示：
 * accounts的长度将在[1，1000]的范围内。
 * accounts[i]的长度将在[1，10]的范围内。
 * accounts[i][j]的长度将在[1，30]的范围内。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/accounts-merge
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class January18 {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        return new Account(accounts).merge();
    }
    public static void main(String[] args) {
        List<List<String>> accounts = new ArrayList<>();
        List<String> list1 = new ArrayList<>();
        list1.add("John");
        list1.add("johnsmith@mail.com");
        list1.add("john00@mail.com");
        accounts.add(list1);

        List<String> list2 = new ArrayList<>();
        list2.add("John");
        list2.add("johnnybravo@mail.com");
        accounts.add(list2);

        List<String> list3 = new ArrayList<>();
        list3.add("John");
        list3.add("johnsmith@mail.com");
        list3.add("john_newyork@mail.com");
        accounts.add(list3);

        List<String> list4 = new ArrayList<>();
        list4.add("Mary");
        list4.add("mary@mail.com");
        accounts.add(list4);

        List<List<String>> lists = new January18().accountsMerge(accounts);
        lists.forEach(System.out::println);

    }

    private class Account {
        List<List<String>> accounts;

        public Account(List<List<String>> accounts) {
            this.accounts = accounts;
        }

        // 判断两个账户是否是一个账户
        private boolean isOneAccount(List<String> list1, List<String> list2) {
            // 先移除账户名，因为是根据邮箱地址判断的
            for (String a : list1) {
                if (list2.contains(a)) {
                    return true;
                }
            }
            return false;
        }


        // 合并
        public List<List<String>> merge() {
            // 先将各个账户名称抽离出来
            List<String> names = new ArrayList<>();
            this.accounts.forEach(val -> {
                names.add(val.get(0));
                val.remove(0);
            });
            accounts.forEach(System.out::println);
            System.out.println("names=========" + names);
            System.out.println("-------------------------------------------------------");

            boolean ac = true; //设置一个信号量，用来判断是否存在合并的可能，如果存在，为tr
            out:
            while (ac) {
                ac = false;
                for (int i = 0; i < accounts.size(); i++) {
                    for (int j = 0; j < accounts.size(); j++) {
                        if (i == j) continue;
                        if (isOneAccount(accounts.get(i), accounts.get(j))) { // 如果能合并，证明是一个集合的
                            System.out.println(i + "+" + j + "======true");
                            // 先把信号量设置为true
                            ac = true;
                            //--- 合并两个集合
                            accounts.get(i).addAll(accounts.get(j));
                            Set<String> set = new HashSet<>(accounts.get(i));
                            accounts.get(i).clear();
                            accounts.get(i).addAll(set);
                            //---
                            accounts.remove(j);
                            names.remove(j);
                        }
                    }
                    if (ac) continue out;
                }
            }

            // 将用户名和邮件地址合并起来
            for (int i = 0; i < accounts.size(); i++) {
                accounts.get(i).add(0, names.get(i));
            }
            return accounts;
        }
    }
}
